class Solution {
public:
    pair<Node*,Node*> change(Node* root){
        if(!root){
            return {NULL,NULL};
        }
    
        pair<Node*,Node*> l = change(root->left);
        pair<Node*,Node*> r = change(root->right);

        if(root->left && l.first){
            l.first->right = root;
            root->left = l.first;
        }
    
        if(root->right && r.second){
            r.second->left = root;
            root->right = r.second;
        }
        
        if(!r.first || root->val > r.first->val){
            r.first = root;
        }
        if(!l.second || root->val < l.second->val){
            l.second = root;
        }
        return {r.first,l.second};
    }
                                        
    Node* treeToDoublyList(Node* root) {
        if(!root){
            return NULL;
        }
        Node* head = root;
        Node* tail = root;
        while(head->left){
            head = head->left;
        }
        while(tail->right){
            tail = tail->right;
        }
        
        change(root);
        head->left = tail;
        tail->right = head;
        return head;
    }
};
